/*
 * @Author: liusheng
 * @Date: 2022-04-20 12:45:41
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-20 17:49:21
 * @Description: 剑指 Offer II 035. 最小时间差
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 */
#include "header.h"
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> times;
        for (auto str: timePoints)
        {
            size_t colonIndex = str.find(':');
            int hour = stoi(str.substr(0,colonIndex));
            int minutes = hour * 60;
            minutes += stoi(str.substr(colonIndex + 1));

            times.push_back(minutes);
            // printf("time:%d,%d\n",minutes,1440 + minutes);
            //if hour <- 12,may be has min diff with last day after 12
            if (hour <= 12)
            {
                times.push_back(1440 + minutes);
            }
        }

        sort(times.begin(),times.end());
        int n = times.size();
        int minDiff = 1500;//bigger then the max diff 1440
        for (int i = 1; i < n; ++i)
        {
            int diff = times[i] - times[i-1];
            if (diff < minDiff)
            {
                minDiff = diff;
            }
        }
        return minDiff;
    }
};

/*
Time:O(nlog(n))
Space:O(1)
*/
class Solution2 {
public:
    int findMinDifference(vector<string>& timePoints) {
        int n = timePoints.size();
        //minutes is from 0 - 1439
        //so if n > 1440 there must hava duplicate value
        if (n > 1440)
        {
            return 0;
        }
        
        sort(timePoints.begin(),timePoints.end());
        auto getMinutes = [] (const string & str) -> int
        {
            return ((str[0] - '0') * 10 + str[1]) * 60 + (str[3] - '0') * 10 + (str[4] - '0');
        };
        
        int minDiff = 1550;//bigger than the max diff 1339
        for (int i = 1; i < n; ++i)
        {
            int diff = getMinutes(timePoints[i]) - getMinutes(timePoints[i-1]);
            if (diff < minDiff)
            {
                minDiff = diff;
            }
        }
        
        int headMinutes = getMinutes(timePoints[0]);
        int tailMinutes = getMinutes(timePoints[n-1]);
        const int minutesPerDay = 1440;
        //the minist diff may be in the head -tail diff,another day
        //diff with last night
        int headTailDiff = minutesPerDay + headMinutes - tailMinutes;
        
        return min(minDiff,headTailDiff);
    }
};